# 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。
# 假设输入的数组的任意两个数字都互不相同。
# 空树可以是二叉搜索树，否则，左子树所有节点小于根节点，右子树所有节点大于根节点，左右子树也是二叉搜索树

def isSearchTree(sequence):
    if not sequence:
        return False
    if len(sequence)==1:
        return True
    length = len(sequence)
    root = sequence[-1]
    i=0
    while sequence[i]<root:
        i+=1
    pos = i
    for j in range(pos,len(sequence)-1):
        if sequence[j]<root:
            return False

    left_s = sequence[:pos]
    right_s = sequence[pos:-2]

    leftS = True
    rightS = True

    if len(left_s)>0:
        leftS = isSearchTree(left_s)
    if len(right_s)>0:
        rightS = isSearchTree(right_s)

    return leftS and rightS

